package algorithm.sort;

import java.sql.Array;
import java.util.Arrays;

/**
 * @Author liuhaoqi
 * @Date 2020/12/20 10:29
 * @Version 1.0
 * 归并排序
 */
public class MergeSort {

    public static void main(String[] args) {
        int[] arr = {1, 2, 6, 7, 8, 9, 9, 1, 7};
        int[] arrs = mergeSort(arr);
        for (int i : arrs) {
            System.out.println(i);
        }
    }

    /**
     * 归并排序 递归版
     * @param array
     * @return
     */
    public static int[] mergeSort(int[] array) {
        if (array.length <2) return array;
        int mid = array.length / 2;
        int[] left = Arrays.copyOfRange(array, 0, mid);
        int[] right = Arrays.copyOfRange(array, mid, array.length);
        return merge(mergeSort(left), mergeSort(right));
    }

    public static int[] merge(int[] left, int[] right) {
        int[] result = new int[left.length + right.length];
        for (int index = 0, i = 0, j = 0; index < result.length; index++) {
            //如果穷尽了左边的数组，那就直接把右侧的数组赋值给当前索引
            if(i>=left.length)
                result[index] = right[j++];
            //如果穷尽了右边的数组，那就直接把左边的数组赋值到当前索引
            else if (j>=right.length)
                result[index] = left[i++];
            //如果左边的数大于右边的数，那就把右边的数赋值给当前索引
            else if(left[i] >right[j])
                result[index] = right[j++];
            //如果右边的数大于左边的数，那就把左边的数赋值给当前索引
            else
                result[index] = left[i++];
        }
        return result;
    }

    }

